package 滑动窗口And双指针.双指针;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/10 14:24
 */
public class lc18四数之和 {

    /*
      整的挺花哨

      这不就是 组合求和嘛!
      只不过 回溯会超时!

     */

    /*
     还是 拆分 ,
     固定一个数 先拆分 成 三数之和
     在固定一个数, 拆分成两数之和!
     */

    /*
     [1000000000,1000000000,1000000000,1000000000]
     -294967296

     要做溢出判断, 否则专门有上面这个 case 卡着
     如果 不是lc 这种 给你 显示测试用例的话, 你能想到吗?
     if(nums[x] > 0 && target < 0){ 过滤一下这种数据
                break;
            }

       直接 用 long

     */


    // 建议后面 不要用  set 去重了, 直接用 下标去重!
    public List<List<Integer>> solution(int nums[], int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        Set<Integer> set_x = new HashSet<>();
        // 固定枚举 x
        for (int x = 0; x < nums.length - 3; x++) {
            if(nums[x] > 0 && target < 0){
                break;
            }
            if (set_x.contains(nums[x])) {
                continue;
            }
            set_x.add(nums[x]); // 去重 x

            long rest_x = target - nums[x];
            Set<Integer> set_y = new HashSet<>();
            // 固定枚举 y
            for (int y = x + 1; y < nums.length - 2; y++) {
                if (set_y.contains(nums[y])) {
                    continue;
                }
                set_y.add(nums[y]);  // 去重y
                long rest_y = rest_x - nums[y];
                int l = y + 1, r = nums.length - 1;
                //  双指针
                while (l < r) {
                    long temp = nums[l] + nums[r];
                    if (temp == rest_y) {
                        ans.add(Arrays.asList(nums[x], nums[y], nums[l], nums[r]));
                        // 去重
                        while ( l < r && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        while (l < r && nums[r] == nums[r - 1]) {
                            r--;
                        }
                        l++;
                        r--;
                    } else if (temp < rest_y) {
                        l++;
                    } else {
                        r--;
                    }
                }

            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(1000_000_000 * 4);
    }

}
